//给定一棵二叉搜索树，请找出其中第k大的节点。 
//
// 
//
// 示例 1: 
//
// 输入: root = [3,1,4,null,2], k = 1
//   3
//  / \
// 1   4
//  \
//   2
//输出: 4 
//
// 示例 2: 
//
// 输入: root = [5,3,6,2,4,null,null,1], k = 3
//       5
//      / \
//     3   6
//    / \
//   2   4
//  /
// 1
//输出: 4 
//
// 
//
// 限制： 
//
// 1 ≤ k ≤ 二叉搜索树元素个数 
// Related Topics 树 
// 👍 54 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

/**
 * Java：二叉搜索树的第k大节点
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P剑指_offer_54_ErChaSouSuoShuDeDiKdaJieDianLcof {
    public static void main(String[] args) {
        Solution solution = new P剑指_offer_54_ErChaSouSuoShuDeDiKdaJieDianLcof().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 中序遍历逆序，提前返回
     */
    class Solution {
        int res;
        int k;
        public int kthLargest(TreeNode root, int k) {
            this.k = k;
            traverse(root);
            return res;
        }

        private void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            traverse(root.right);
            if(--k == 0) {
                res = root.val;
                return;
            }
            traverse(root.left);
        }
    }

    /**
     * 中规中矩的中序遍历
     */
    //class Solution {
    //    List<Integer> list = new ArrayList<>();
    //
    //    public int kthLargest(TreeNode root, int k) {
    //        traverse(root);
    //        return list.get(list.size() - 1 - (k - 1));
    //    }
    //
    //    private void traverse(TreeNode root) {
    //        if (root == null) {
    //            return;
    //        }
    //        traverse(root.left);
    //        list.add(root.val);
    //        traverse(root.right);
    //    }
    //}
//leetcode submit region end(Prohibit modification and deletion)

}